#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

const ll N = 2e5 + 10, INF = 4e18;

ll n, m;
vector<pair<ll, ll>> g[N];
ll dis[2][N], vis[2][N];

struct node {
    ll x, d, op;
};

struct cmp {
    bool operator()(const node& a, const node& b) const {
        return a.d > b.d;  // 小根堆
    }
};

void solve()
{
    memset(dis, 0x3f, sizeof dis);
    cin >> n >> m;
    for (ll i = 1;i <= m;i++) {
        ll x, y, w;cin >> x >> y >> w;
        g[x].push_back({ y,w });
        g[y].push_back({ x,w });
    }
    dis[0][0] = dis[1][0] = 0;
    for (ll i = 1;i <= n;i++) {
        ll w;cin >> w;
        g[0].push_back({ i,w });
        g[i].push_back({ 0,w });
    }
    priority_queue<node, vector<node>, cmp> q;
    q.push({ 0,0,0 });
    while (!q.empty()) {
        auto [x, d, op] = q.top();q.pop();
        if (vis[op][x]) continue;
        vis[op][x] = 1;
        for (auto [y, w] : g[x]) {
            if (dis[op][y] > d + w) {
                dis[op][y] = d + w;
                q.push({ y,dis[op][y],op });
            }
            if (op == 0 && dis[1][y] > d && x != 0) {
                dis[1][y] = d;
                q.push({ y,dis[1][y],1 });
            }
        }
    }

    ll ans = 0;
    for (ll i = 1;i <= n;i++) {
        ans = max(ans, min(dis[0][i], dis[1][i]));
    }
    cout << ans << '\n';
}

signed main()
{
    //ios::sync_with_stdio(0);
    //cin.tie(0);cout.tie(0);
#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
    std::istringstream in(R"()");
    std::cin.rdbuf(in.rdbuf());
#endif
    ll T = 1;
    //cin>>T;
    for (ll i = 1;i <= T;i++) {
        solve();
    }
}